#ifndef __MCS__STRING__HPP
#define __MCS__STRING__HPP

#include <algorithm>
#include <cassert>
#include <cstring>
#include <deque>
#include <map>
#include <sstream>
#include <string>
#include <typeinfo>
#include <vector>

/// Root class for all value classes
class Void {};

/// Adds implicit data sharing to std::string.
/**
@todo Implement case-insensitive locale-aware comparison.
*/
class String : public Void
{
public:
	String() : d(shared_null) {}
	String(char const * str) : d(new StringData(str)) {}
	String(std::string const & str) : d(new StringData(str)) {}

	std::string const & string() const { return d->string; }
	std::string * stringPtr() { return &d->string; }
	std::string & stringRef() { return d->string; }

	operator char const *() const { return d->string.c_str(); }
	operator std::string const & () const { return d->string; }

	bool operator==(std::string const & str) const { return d->string == str; }
	bool operator==(String const & other) const    { return d == other.d || d->string == other.d->string; }
	bool operator==(char const * str) const        { return d->string == str; }
	bool operator!=(std::string const & str) const { return d->string != str; }
	bool operator!=(String const & other) const    { return d != other.d && d->string != other.d->string; }
	bool operator!=(char const * str) const        { return d->string != str; }
	bool operator<(std::string const & str) const  { return d->string < str; }
	bool operator<(String const & other) const     { return d->string < other.d->string; }
	bool operator<(char const * str) const         { return d->string < str; }
	bool operator>(std::string const & str) const  { return d->string > str; }
	bool operator>(String const & other) const     { return d->string > other.d->string; }
	bool operator>(char const * str) const         { return d->string > str; }
	bool operator<=(std::string const & str) const { return d->string <= str; }
	bool operator<=(String const & other) const    { return d->string <= other.d->string; }
	bool operator<=(char const * str) const        { return d->string <= str; }
	bool operator>=(std::string const & str) const { return d->string >= str; }
	bool operator>=(String const & other) const    { return d->string >= other.d->string; }
	bool operator>=(char const * str) const        { return d->string >= str; }

	String & operator+=(std::string const & str) { d->string += str; return *this; }
	String & operator+=(String const & other)    { d->string += other.d->string; return *this; }
	String & operator+=(char const * str)        { d->string += str; return *this; }
	String operator+(std::string const & str) const { String r(*this); r += str; return r; ; }
	String operator+(String const & str) const      { String r(*this); r += str; return r; ; }
	String operator+(char const * str) const        { String r(*this); r += str; return r; ; }

	bool empty() const { return d->string.empty(); }
	size_t size() const { return d->string.size(); }
	void resize(size_t len) { d->string.resize(len); }
	void resize(size_t len, char c) { d->string.resize(len, c); }
	size_t capacity() const { return d->string.capacity(); }
	void reserve(size_t len) { d->string.reserve(len); }
	void clear() { d = shared_null; }
	
	char at(size_t i) const { return d->string.at(i); }

	void push_back(char c) { d->string.push_back(c); }

	int compare(std::string const & str) const { return d->string.compare(str); }
	int compare(char const * str) const        { return d->string.compare(str); }
	
	int compare(String const & other) const
	{
		if(d == other.d) return 0;
		return d->string.compare(other.d->string);
	}

	String substr(size_t offs) const { return new StringData(d->string, offs); }
	String substr(size_t offs, size_t count) const { return new StringData(d->string, offs, count); }

	void swap(String & other) { d.swap(other.d); }
private:
	class StringData
	{
	public:
		int refCounter;
		std::string string;

		StringData() : refCounter(0), string() {}
		StringData(char const * str) : refCounter(0), string(str) {}
		StringData(std::string const & str) : refCounter(0), string(str) {}
		StringData(size_t n, char c) : refCounter(0), string(n, c) {}
		StringData(std::string const & str, size_t offs) : refCounter(0), string(str, offs) {}
		StringData(std::string const & str, size_t offs, size_t count) : refCounter(0), string(str, offs, count) {}
		StringData(StringData const & o) : refCounter(0), string(o.string) {}
		StringData & operator=(StringData const & o) { string = o.string; return *this; }
	};

	class DataPtr
	{
	public:
		DataPtr(StringData * data) : p(data) { ++p->refCounter; }
		DataPtr(DataPtr const & other) : p(other.p) { ++p->refCounter; }
		~DataPtr() { if(!--p->refCounter) delete p; }

		DataPtr & operator =(DataPtr const & other)
		{
			++other.p->refCounter;
			if(!--p->refCounter) delete p;
			p = other.p;
			return *this;
		}

		void detach()
		{
			if(p->refCounter > 1)
			{
				StringData * pp = new StringData(*p);
				--p->refCounter; p = pp; ++p->refCounter;
			}
		}

		StringData const * data() const { return p; }
		StringData * data() { detach(); return p; }
		StringData const * constData() const { return p; }

		StringData const * operator->() const { return p; }
		StringData * operator->() { detach(); return p; }

		bool operator==(DataPtr const & other) const { return p == other.p; }
		bool operator!=(DataPtr const & other) const { return p != other.p; }

		void swap(DataPtr & other) { std::swap(p, other.p); }
	private:
		StringData * p;
	};

	static DataPtr shared_null;
	DataPtr d;

	String(StringData * p) : d(p) {}
};

inline std::ostream & operator<<(std::ostream & str, String const & s)
{
	return str << s.string();
}

namespace std { inline void swap(String & a, String & b) { a.swap(b); } }

#endif //__MCS__STRING__HPP